BZOJ1013【JSOI2008】球形空间产生器 <高斯消元>

Problem

【JSOI2008】球形空间产生器

Description

有一个球形空间产生器能够在维空间中产生一个坚硬的球体。
现在，你被困在了这个维球体中，你只知道球面上个点的坐标，你需要以最快的速度确定这个维球体的球心坐标，以便于摧毁这个球形空间产生器。

Input

第一行是一个整数。
接下来的行，每行有个实数，表示球面上一点的维坐标。
每一个实数精确到小数点后位，且其绝对值都不超过。

Output

有且只有一行，依次给出球心的维坐标（个实数），两个实数之间用一个空格隔开。
每个实数精确到小数点后位，数据保证有解，你的答案必须和标准输出一模一样才能够得分。

Sample Input

2
0.0 0.0
-1.0 1.0
1.0 0.0

Sample Output

1	0.500 1.500

HINT

给出两个定义：

球心：到球面上任意一点距离都相等的点。
距离：设两个维空间上的点的坐标为,，则的距离定义为：

标签：高斯消元

Solution

高消裸题。

将第个点单独分出来，将其与前个点分别联立形成个方程，高消即可求得球心坐标。

设球心为，第个点为。对于前个点中的一个点，设坐标为。那么一定有

展开得

移项化简

直接高斯消元解方程组，时间复杂度。

注意行末不要输出空格

Code

#include <bits/stdc++.h>
#define EPS 1e-8
using namespace std;
typedef double dnt;
int n; dnt p[15][15], f[15][15];
dnt sqr(dnt x) {return x*x;}
bool Gauss() {
    for (int i = 1, t; i <= n; i++) {
        for (t = i; t <= n; t++) if (fabs(f[t][i]) >= EPS) break;
        if (t > n) return false; swap(f[i], f[t]);
        for (int j = 1; j <= n; j++) if (i^j) {
            dnt div = f[j][i]/f[i][i];
            for (int k = 1; k <= n+1; k++)
                f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++) f[i][n+1] /= f[i][i];
    return true;
}	
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n+1; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lf", p[i]+j);
    for (int i = 1, j = n+1; i <= n; i++)
        for (int k = 1; k <= n; k++)
            f[i][k] = p[i][k]-p[j][k], 
            f[i][n+1] += (sqr(p[i][k])-sqr(p[j][k]))/2;
    Gauss();
    for (int i = 1; i <= n; i++)
        if (i^n) printf("%.3lf ", f[i][n+1]);
        else printf("%.3lf", f[i][n+1]);
    return 0;
}